//给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。 
//
// 
//
// 示例 1: 
//
// 
//输入: n = 13, k = 2
//输出: 10
//解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
// 
//
// 示例 2: 
//
// 
//输入: n = 1, k = 1
//输出: 1
// 
//
// 
//
// 提示: 
//
// 
// 1 <= k <= n <= 10⁹ 
// 
// Related Topics 字典树 👍 314 👎 0

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class _440_KThSmallestInLexicographicalOrder {
    public static void main(String[] args) {
        Solution solution = new _440_KThSmallestInLexicographicalOrder().new Solution();
        System.out.println(solution.findKthNumber(681692778,351251360));
    }

    class Solution {
        public int findKthNumber(int n, int k) {
            int cur = 1;//第一字典序小的(就是1)
            int prefix = 1;// 前缀从1开始
            while (cur < k) {
                int tmp = count(n, prefix); //当前prefix峰的值
                if (tmp + cur > k) {// 找到了
                    prefix *= 10; //往下层遍历
                    cur++;//一直遍历到第K个推出循环
                } else {
                    prefix++;//去下个峰头(前缀)遍历
                    cur += tmp;//跨过了一个峰(前缀)
                }
            }//退出循环时 cur==k 正好找到
            return prefix;
        }

        private int count(int n, int prefix) {
            //不断向下层遍历可能一个乘10就溢出了, 所以用long
            long cur = prefix;
            long next = cur + 1;//下一个前缀峰头
            int count = 0;
            while (cur <= n) {
                count += Math.min(n + 1, next) - cur;//下一峰头减去此峰头
                // 如果说刚刚prefix是1，next是2，那么现在分别变成10和20
                // 1为前缀的子节点增加10个，十叉树增加一层, 变成了两层

                // 如果说现在prefix是10，next是20，那么现在分别变成100和200，
                // 1为前缀的子节点增加100个，十叉树又增加了一层，变成了三层
                cur *= 10;
                next *= 10; //往下层走
            }
            return count;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 超时了
    class Solution1 {
        public int findKthNumber(int n, int k) {
            String[] nums = new String[n];
            for (int i = 0; i < n; i++) {
                nums[i] = (i + 1) + "";
            }
            List<String> list = Arrays.asList(nums);
            Collections.sort(list);
            for (String s : list) {
                System.out.print(s + " ");
            }
            return Integer.parseInt(list.get(k - 1));

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}